(define (make-leaf symbol weight)
    (list `leaf symbol weight)
)
(define (leaf? object)
    (eq? (car object) `leaf)
)
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
    (list 
        left
        right
        (append 
            (symbols left)
            (symbols right)
        )
        (+ (weight left) (weight right))
    )
)

(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)
    )
)
(define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (cadddr tree)
    )
)


(define (encode message tree)
    (if (null? message)
        `()
        (append 
            (encode-symbol (car message) tree)
            (encode (cdr message) tree)
        )
    )
)
(define (encode-symbol my-symbol tree)
    (if (leaf? tree)
        `()
        (if (has-symbol? my-symbol (symbols (left-branch tree)))
            (append 
                (list `0)
                (encode-symbol my-symbol (left-branch tree))
            )
            (append
                (list `1)
                (encode-symbol my-symbol (right-branch tree))
            )
        )
    )
)
(define (has-symbol? my-symbol list-item)
    (cond 
        ((null? list-item) #f)
        ((eq? my-symbol (car list-item)) #t)
        (else (has-symbol? my-symbol (cdr list-item)))
    )
)



(define sample-tree
    (make-code-tree
        (make-leaf `A 4)
        (make-code-tree 
            (make-leaf `B 2)
            (make-code-tree
                (make-leaf `D 1)
                (make-leaf `C 1)
            )
        )
    )
)
(display sample-tree)
(newline)
(define sample-message `(A D A B B C A))
(display (encode sample-message sample-tree))
(exit)